class Trie(Node):
	def __init__(self) -> None:
		super().__init__(None) # super():子类调用父类的一个方法。

	def __contains__(self,key):
		return self[key] is not None

	def __getitem__(self,key):
		state = self

		for char in key:
			state = state._children.get(char)
			if state is None:
				return None

		return state._value

	def __setitem__(self,key,value):
		state = self
		for i,char in enumerate(key):
			if i < len(key)-1 :
				state = state._add_child(char,None,False)
			else:
				state = state._add_child(char,value,True)


# 字典树の节点Node(data struture + Method)
class Node(object):
	def __init__(self,value) -> None: # return None; 构造函数
		self._children = {}
		self._value = value

	def _add_child(self, char, value, overwrite=False):
	# 给 当前Node 添加 子节点
		child = self._children.get(char) # 获取 当前的char(词)对应的child
		# 因为每个节点至少都知道自己的子节点和对应的边,以及自己是否已经是一个词？

		if child is None: # 如果 子节点 = None,也就是当前的词已经到达末路
			child = Node(value)	# 那么子节点 = Node(value);添加了 新节点
			self._children[char] = child # 将当前的词char,完结,指针指向 新添加的Node(value) 子节点
		elif overwrite: # 如果存在child
			child._value = value # 则子节点的value = 

		return child

